#include <vector>
#include <algorithm>

class MinHeap {
    std::vector<int> heap;

    void siftUp(int i) {
        // Условие Min-Heap: родитель должен быть МЕНЬШЕ ребенка
        while (i > 0 && heap[(i - 1) / 2] > heap[i]) {
            std::swap(heap[i], heap[(i - 1) / 2]);
            i = (i - 1) / 2;
        }
    }

    void siftDown(int i) {
        int minIdx = i;
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        // Ищем МИНИМАЛЬНОЕ значение среди родителя и детей
        if (l < heap.size() && heap[l] < heap[minIdx]) minIdx = l;
        if (r < heap.size() && heap[r] < heap[minIdx]) minIdx = r;
        if (i != minIdx) {
            std::swap(heap[i], heap[minIdx]);
            siftDown(minIdx);
        }
    }

public:
    void insert(int val) {
        heap.push_back(val);
        siftUp(heap.size() - 1);
    }

    int extractMin() {
        if (heap.empty()) return -1;
        int res = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        if (!heap.empty()) siftDown(0);
        return res;
    }
};